package Algorithm.sort.basic;

import java.util.Arrays;

/**
 * **算法思想（二路归并）**：
 * ①初始时，将每个记录看成一个单独的有序序列，则n个待排序记录就是n个长度为 1的有序子序列
 * ②对所有相邻的有序子序列进行两两合并。在第一趟归并中会得到n/2个长度为2或1	的有序子序列
 * ③重复②，直到得到长度为n的有序序列为止
 *
 * **性能**：每趟归并的时间复杂度为O(n)，共需趟归并logn趟，所以**时间复杂度最好最坏都为O(nlogn)**。递归栈深度为logn，数组排序时需要长度为n的辅助数组，故总的**空间复杂度为O(n)**。稳定
 *
 * **适用场景**：链表排序，外部排序（多路归并）
 */
public class MergeSort {

    //辅助数组
    private static int[] B;

    public static void main(String[] args) {
        int[] A = new int[]{5,6,1,2,3,6,9};
        B = new int[A.length];
        mergeSort(A, 0, A.length-1);
        System.out.println(Arrays.toString(A));
    }

    //利用递归实现
    static void mergeSort(int[] A, int low, int high) {
        if(low<high) {
            int mid=(low+high)/2;//从中间划分两个子序列
            mergeSort(A,low,mid);//对左侧子序列进行递归排序
            mergeSort(A,mid+1,high);//对右侧子序列进行递归排序
            merge(A,low,mid,high);//归并
        }
    }

    //merge函数的功能是将相邻的两段有序子序列A[low,mid]和A[mid+1,high]归并为一个有序序列
    static void merge(int[] A, int low, int mid, int high) {
        //将A中两个有序子序表元素复制到B的对应位置中
        for (int i = low; i <= high; i++) {
            B[i] = A[i];
        }
        int i,j,k;
        for(i=low, j=mid+1, k=i;i<=mid&&j<=high;k++) {
            //比较两个子序表中的元素,将较小值复制到A中
            //相等时左边的优先复制，可确保稳定性
            if(B[i]<=B[j])
                A[k] = B[i++];
            else
                A[k] = B[j++];
        }
        //未检测完的表直接复制到有序表的后面
        while(i<=mid) A[k++]=B[i++];
        while(j<=high) A[k++]=B[j++];
    }
}
/**
 * **简评**：内部排序中，在进行数组的排序时，快排不需要额外辅助空间，故性能优于归并排序，**而在进行链表的排序时（见DataStructure.linkList.SortList.Java），归并排序不需要数组作为辅助空间，并且归并排序能够更均匀的划分列表，且归并排序具有稳定性，故此时总体优于快排**。
 * 此外，归并排序还是一种外部排序算法，在对大型的磁盘文件内的数据进行排序时，内存可能不够将数据一次全部加载到内存进行排序，此时可根据内存大小将文件划分为n份逐份加载进内存进行内部排序（这里任意排序算法均可），
 * 在磁盘中得到n份有序的数据，然后每次从这n个文件中各取一个数据（简化）加载到内存，在内存中比较出这n个数据的最值写入磁盘，然后从这个最值的文件中再取出一个数参与比较，直到扫描完成这n个文件，这就是n路归并排序的大概思想，
 * 具体的细节可参考下面两个资料
 *  [多路归并排序](https://www.bilibili.com/video/BV1zu411S76W)
 *  [大数据中的归并排序(Merge Sort)](https://www.jianshu.com/p/be65c3deb7fc)
 */